#include <stdio.h>
#include <stdlib.h>

// 定义二叉排序树节点
typedef struct Node {
    int data;               // 节点数据
    struct Node *left;      // 左子树
    struct Node *right;     // 右子树
} Node;
// 插入节点函数
Node* insert(Node* root, int data) {
    if (root == NULL) {  // 如果树为空，创建新的节点
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }

    if (data < root->data) {
        root->left = insert(root->left, data);  // 插入左子树
    } else if (data > root->data) {
        root->right = insert(root->right, data); // 插入右子树
    }
    return root;  // 返回根节点
}
// 查找节点函数
Node* search(Node* root, int key) {
    if (root == NULL || root->data == key) {
        return root;  // 找到或树为空
    }

    if (key < root->data) {
        return search(root->left, key);  // 在左子树中查找
    } else {
        return search(root->right, key);  // 在右子树中查找
    }
}
// 查找最小值节点（用于删除时找到中序后继）
Node* findMin(Node* root) { //找中序遍历后继结点
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

// 删除节点函数
Node* deleteNode(Node* root, int key) {
    if (root == NULL) {
        return root;  // 树为空
    }

    if (key < root->data) {
        root->left = deleteNode(root->left, key);  // 在左子树中删除
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key);  // 在右子树中删除
    } else {
        // 找到节点
        // 如果是叶子节点，也在此删除
        if (root->left == NULL) {
            Node* temp = root->right;  // 只有右子树
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;  // 只有左子树
            free(root);
            return temp;
        }

        // 有两个子节点，找到中序后继
        //两种方法：1.用中序前驱替换（左子树找最大） 2.用中序后继替换（右子树找最小）
        Node* temp = findMin(root->right);//右子树上的最小值
        root->data = temp->data;  // 用后继节点（右子树上最小值）值替换
        root->right = deleteNode(root->right, temp->data);  // 删除后继节点（右子树上最小值）
    }

    return root;  // 返回根节点
}
// 中序遍历函数
void inorderTraversal(Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}
int main() {
    Node* root = NULL;

    // 插入节点
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);

    printf("Inorder traversal of the given tree: ");
    inorderTraversal(root);
    printf("\n");

    // 查找节点
    int key = 40;
    if (search(root, key) != NULL) {
        printf("Element %d found in the tree.\n", key);
    } else {
        printf("Element %d not found in the tree.\n", key);
    }

    // 删除节点
    printf("Deleting 20\n");
    root = deleteNode(root, 20);
    inorderTraversal(root);
    printf("\n");

    printf("Deleting 30\n");
    root = deleteNode(root, 30);
    inorderTraversal(root);
    printf("\n");

    printf("Deleting 50\n");
    root = deleteNode(root, 50);
    inorderTraversal(root);
    printf("\n");

    return 0;
}
